{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #城墙防线"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: rampartDefensiveLine"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #城墙防线"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "在探险营地间，小扣意外发现了一片城墙遗迹，在探索期间，却不巧遇到迁徙中的兽群向他迎面冲来。情急之下小扣吹响了他的苍蓝笛，随着笛声响起，遗迹中的城墙逐渐发生了横向膨胀。\n",
    "已知 `rampart[i] = [x,y]` 表示第 `i` 段城墙的初始所在区间。当城墙发生膨胀时，将遵循以下规则：\n",
    "- 所有的城墙会同时膨胀相等的长度；\n",
    "- 每个城墙可以向左、向右或向两个方向膨胀。\n",
    "\n",
    "小扣为了确保自身的安全，需要在所有城墙均无重叠的情况下，让城墙尽可能的膨胀。请返回城墙可以膨胀的 **最大值** 。\n",
    "\n",
    "**注意：**\n",
    "- 初始情况下，所有城墙均不重叠，且 `rampart` 中的元素升序排列；\n",
    "- 两侧的城墙可以向外无限膨胀。\n",
    "\n",
    "**示例 1：**\n",
    ">输入：`rampart = [[0,3],[4,5],[7,9]]`\n",
    ">\n",
    ">输出：`3`\n",
    ">\n",
    ">解释：如下图所示：\n",
    ">`rampart[0]` 向左侧膨胀 3 个单位；\n",
    ">`rampart[2]` 向右侧膨胀 3 个单位；\n",
    ">`rampart[1]` 向左侧膨胀 1 个单位，向右膨胀 2 个单位。\n",
    ">不存在膨胀更多的方案，返回 3。\n",
    "![image.png](https://pic.leetcode.cn/1681717918-tWywrp-image.png){:width=750px}\n",
    "\n",
    "**示例 2：**\n",
    ">输入：`rampart = [[1,2],[5,8],[11,15],[18,25]]`\n",
    ">\n",
    ">输出：`4`\n",
    "\n",
    "**提示：**\n",
    "- `3 <= rampart.length <= 10^4`\n",
    "- `rampart[i].length == 2`\n",
    "- `0 <= rampart[i][0] < rampart[i][1] <= rampart[i+1][0] <= 10^8`"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [Nsibyl](https://leetcode.cn/problems/Nsibyl/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [Nsibyl](https://leetcode.cn/problems/Nsibyl/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[[0,3],[4,5],[7,9]]', '[[1,2],[5,8],[11,15],[18,25]]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rampartDefensiveLine(self, rampart: List[List[int]]) -> int:\n",
    "        n = len(rampart)\n",
    "        left = [0]*n \n",
    "        right = [0]*n\n",
    "        left[0] = float('inf')\n",
    "        right[n-1] = float('inf')\n",
    "        for i in range(1,n):\n",
    "            left[i] =  rampart[i][0] - rampart[i-1][1]\n",
    "            right[i-1] = rampart[i][0] - rampart[i-1][1]\n",
    "        def check(x):\n",
    "            rem = 0\n",
    "            for i in range(n):\n",
    "                rem = max(x + rem - left[i],0)\n",
    "                if(rem > right[i]):\n",
    "                    return False \n",
    "            return True\n",
    "        l, r = 0, 10**8\n",
    "        while(l <= r):\n",
    "            m = (l+r)>>1\n",
    "            if(check(m)):\n",
    "                l = m + 1\n",
    "            else:\n",
    "                r = m - 1\n",
    "        return r\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rampartDefensiveLine(self, rampart: List[List[int]]) -> int:\n",
    "        l = 0\n",
    "        r = float('inf')\n",
    "        n = len(rampart)\n",
    "        for i in range(1,n - 1):\n",
    "            r = min(r,rampart[i][0] - rampart[i - 1][1] + rampart[i + 1][0] - rampart[i][1])\n",
    "        \n",
    "        def check(x):\n",
    "            lst = rampart[0][1]\n",
    "            for i in range(1,n - 1):\n",
    "                left = rampart[i][0] - lst\n",
    "                if left >= x:\n",
    "                    lst = rampart[i][1]\n",
    "                    continue\n",
    "                cnt = x - left\n",
    "                right = rampart[i + 1][0] - rampart[i][1]\n",
    "                if right >= cnt:\n",
    "                    lst = rampart[i][1] + cnt\n",
    "                else:\n",
    "                    return False\n",
    "            return True\n",
    "        \n",
    "        while l <= r:\n",
    "            mid = l + (r - l) // 2\n",
    "            if check(mid):\n",
    "                l = mid + 1\n",
    "            else:\n",
    "                r = mid - 1\n",
    "        return l - 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rampartDefensiveLine(self, rampart: List[List[int]]) -> int:\n",
    "        l = 0\n",
    "        r = float('inf')\n",
    "        n = len(rampart)\n",
    "        for i in range(1,n - 1):\n",
    "            r = min(r,rampart[i][0] - rampart[i - 1][1] + rampart[i + 1][0] - rampart[i][1])\n",
    "        \n",
    "        def check(x):\n",
    "            lst = rampart[0][1]\n",
    "            for i in range(1,n - 1):\n",
    "                left = rampart[i][0] - lst\n",
    "                if left >= x:\n",
    "                    lst = rampart[i][1]\n",
    "                    continue\n",
    "                cnt = x - left\n",
    "                right = rampart[i + 1][0] - rampart[i][1]\n",
    "                if right >= cnt:\n",
    "                    lst = rampart[i][1] + cnt\n",
    "                else:\n",
    "                    return False\n",
    "            return True\n",
    "        \n",
    "        while l <= r:\n",
    "            mid = l + (r - l) // 2\n",
    "            if check(mid):\n",
    "                l = mid + 1\n",
    "            else:\n",
    "                r = mid - 1\n",
    "        return l - 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rampartDefensiveLine(self, rampart: List[List[int]]) -> int:\n",
    "        n = len(rampart)\n",
    "        left = [0]*n \n",
    "        right = [0]*n\n",
    "        left[0] = float('inf')\n",
    "        right[n-1] = float('inf')\n",
    "        for i in range(1,n):\n",
    "            left[i] =  rampart[i][0] - rampart[i-1][1]\n",
    "            right[i-1] = rampart[i][0] - rampart[i-1][1]\n",
    "        def check(x):\n",
    "            rem = 0\n",
    "            for i in range(n):\n",
    "                rem = max(x + rem - left[i],0)\n",
    "                if(rem > right[i]):\n",
    "                    return False \n",
    "            return True\n",
    "        l, r = 0, 10**8\n",
    "        while(l <= r):\n",
    "            m = (l+r)>>1\n",
    "            if(check(m)):\n",
    "                l = m + 1\n",
    "            else:\n",
    "                r = m - 1\n",
    "        return r\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rampartDefensiveLine(self, rampart: List[List[int]]) -> int:\n",
    "        def fail(l):\n",
    "            last = -inf\n",
    "            for a, b in rampart:\n",
    "                if last > a:\n",
    "                    return 1\n",
    "                left = max(l - a + last, 0)\n",
    "                last = b + left\n",
    "            return 0\n",
    "\n",
    "        return bisect_left(range(rampart[-1][0] + 1), 1, key=fail) - 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rampartDefensiveLine(self, rampart: List[List[int]]) -> int:\n",
    "        l = 0\n",
    "        r = float('inf')\n",
    "        n = len(rampart)\n",
    "        for i in range(1,n - 1):\n",
    "            r = min(r,rampart[i][0] - rampart[i - 1][1] + rampart[i + 1][0] - rampart[i][1])\n",
    "        \n",
    "        def check(x):\n",
    "            lst = rampart[0][1]\n",
    "            for i in range(1,n - 1):\n",
    "                left = rampart[i][0] - lst\n",
    "                if left >= x:\n",
    "                    lst = rampart[i][1]\n",
    "                    continue\n",
    "                cnt = x - left\n",
    "                right = rampart[i + 1][0] - rampart[i][1]\n",
    "                if right >= cnt:\n",
    "                    lst = rampart[i][1] + cnt\n",
    "                else:\n",
    "                    return False\n",
    "            return True\n",
    "        \n",
    "        while l <= r:\n",
    "            mid = l + (r - l) // 2\n",
    "            if check(mid):\n",
    "                l = mid + 1\n",
    "            else:\n",
    "                r = mid - 1\n",
    "        return l - 1\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rampartDefensiveLine(self, rampart: List[List[int]]) -> int:\n",
    "        l = 0\n",
    "        r = inf\n",
    "        n = len(rampart)\n",
    "        for i in range(1, n - 1):\n",
    "            r = min(r,rampart[i][0] - rampart[i - 1][1] + rampart[i + 1][0] - rampart[i][1])\n",
    "        \n",
    "        def check(x):\n",
    "            lst = rampart[0][1]\n",
    "            for i in range(1, n - 1):\n",
    "                left = rampart[i][0] - lst\n",
    "                if left >= x:\n",
    "                    lst = rampart[i][1]\n",
    "                else:\n",
    "                    cnt = x - left\n",
    "                    right = rampart[i + 1][0] - rampart[i][1]\n",
    "                    if right >= cnt:\n",
    "                        lst = rampart[i][1] + cnt\n",
    "                    else:\n",
    "                        return False\n",
    "            return True\n",
    "        \n",
    "        while l <= r:\n",
    "            mid = l + (r - l) // 2\n",
    "            if check(mid):\n",
    "                l = mid + 1\n",
    "            else:\n",
    "                r = mid - 1\n",
    "        return l - 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rampartDefensiveLine(self, rampart: List[List[int]]) -> int:\n",
    "        l, r = 0, int(1E9 + 7)\n",
    "        n = len(rampart)\n",
    "        while l + 1 < r:\n",
    "            m = (l + r) // 2\n",
    "            ramp = True\n",
    "            pre = 0\n",
    "            for i in range(1, n):\n",
    "                if rampart[i][0] - rampart[i - 1][1] + pre < 0:\n",
    "                    ramp = False\n",
    "                    break\n",
    "                blank = rampart[i][0] - rampart[i - 1][1] + pre\n",
    "                if blank < m:\n",
    "                    pre = blank - m\n",
    "                else:\n",
    "                    pre = 0\n",
    "            if ramp:\n",
    "                l = m\n",
    "            else:\n",
    "                r = m\n",
    "        return l\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rampartDefensiveLine(self, rampart: List[List[int]]) -> int:\n",
    "        def fail(l):\n",
    "            last = -inf\n",
    "            for a, b in rampart:\n",
    "                if last > a:\n",
    "                    return 1\n",
    "                left = max(l - a + last, 0)\n",
    "                last = b + left\n",
    "            return 0\n",
    "\n",
    "        return bisect_left(range(rampart[-1][0] + 1), 1, key=fail) - 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rampartDefensiveLine(self, rampart: List[List[int]]) -> int:\n",
    "        l = 0\n",
    "        r = float('inf')\n",
    "        n = len(rampart)\n",
    "        for i in range(1, n - 1):\n",
    "            r = min(r, rampart[i][0] - rampart[i - 1][1] + rampart[i + 1][0] - rampart[i][1])\n",
    "        print(r)\n",
    "        def check(x):\n",
    "            lst = rampart[0][1]\n",
    "            for i in range(1, n - 1):\n",
    "                left = rampart[i][0] - lst\n",
    "                if left >= x:\n",
    "                    lst = rampart[i][1]\n",
    "                    continue\n",
    "                cnt = x - left\n",
    "                right = rampart[i + 1][0] - rampart[i][1]\n",
    "                if right >= cnt:\n",
    "                    lst = rampart[i][1] + cnt\n",
    "                else:\n",
    "                    return False\n",
    "            return True\n",
    "\n",
    "        while l <= r:\n",
    "            mid = l + (r - l) // 2\n",
    "            if check(mid):\n",
    "                l = mid + 1\n",
    "            else:\n",
    "                r = mid - 1\n",
    "        return l - 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rampartDefensiveLine(self, rampart: List[List[int]]) -> int:\n",
    "        n = len(rampart)\n",
    "        s = rampart[-1][0] - rampart[0][1]\n",
    "        for x, y in rampart[1:-1]:\n",
    "            s -= y - x\n",
    "        \n",
    "        def check(mx: int) -> bool:\n",
    "            pre_r = rampart[0][1]\n",
    "            for i in range(1, n - 1):\n",
    "                r = rampart[i][1]\n",
    "                l = rampart[i][0] - pre_r\n",
    "                if mx > l:\n",
    "                    r += mx - l\n",
    "                    if r > rampart[i + 1][0]:\n",
    "                        return False\n",
    "                pre_r = r\n",
    "            return True\n",
    "\n",
    "        left = -1\n",
    "        right = s // (n - 2) + 1\n",
    "        while left + 1 < right:\n",
    "            mid = (left + right) // 2\n",
    "            if check(mid):\n",
    "                left = mid\n",
    "            else:\n",
    "                right = mid\n",
    "        return left"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import math\n",
    "class Solution:\n",
    "    def rampartDefensiveLine(self, rampart: List[List[int]]) -> int:\n",
    "        n = len(rampart)\n",
    "        min_gap = rampart[2][0] - rampart[0][1] - (rampart[1][1] - rampart[1][0])\n",
    "        all_gap = 0\n",
    "        l = r = 0\n",
    "        for i in range(1, n):\n",
    "            all_gap += rampart[i][0] - rampart[i-1][1]\n",
    "            if i < n-1:\n",
    "                min_gap = min(min_gap, rampart[i+1][0] - rampart[i-1][1] - (rampart[i][1] - rampart[i][0]))\n",
    "        r = min(min_gap,all_gap//(n-2))\n",
    "        def check(x):\n",
    "            lst = rampart[0][1]\n",
    "            for i in range(1, n-1):\n",
    "                left = rampart[i][0] - lst\n",
    "                if left >= x:\n",
    "                    lst = rampart[i][1]\n",
    "                    continue\n",
    "                cnt = x - left\n",
    "                right = rampart[i+1][0] - rampart[i][1]\n",
    "                if right >= cnt:\n",
    "                    lst = rampart[i][1] + cnt\n",
    "                else:\n",
    "                    return False\n",
    "            return True\n",
    "        while l <= r:\n",
    "            mid = l + (r-l) // 2\n",
    "            if check(mid):\n",
    "                l = mid + 1\n",
    "            else:\n",
    "                r = mid -1\n",
    "        return l-1\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rampartDefensiveLine(self, rampart: List[List[int]]) -> int:\n",
    "        n = len(rampart)\n",
    "        left = [0]*n \n",
    "        right = [0]*n\n",
    "        left[0] = float('inf')\n",
    "        right[n-1] = float('inf')\n",
    "        for i in range(1,n):\n",
    "            left[i] =  rampart[i][0] - rampart[i-1][1]\n",
    "            right[i-1] = rampart[i][0] - rampart[i-1][1]\n",
    "        # print(left)\n",
    "        # print(right)\n",
    "        def check(x):\n",
    "            rem = 0\n",
    "            for i in range(n):\n",
    "                rem = max(x + rem - left[i],0)\n",
    "                if(rem > right[i]):\n",
    "                    return False \n",
    "            return True\n",
    "        l, r = 0, 10**8\n",
    "        while(l <= r):\n",
    "            m = (l+r)>>1\n",
    "            if(check(m)):\n",
    "                l = m + 1\n",
    "            else:\n",
    "                r = m - 1\n",
    "        return r\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rampartDefensiveLine(self, rampart: List[List[int]]) -> int:\n",
    "        l = 0\n",
    "        r = float('inf')\n",
    "        n = len(rampart)\n",
    "        for i in range(1,n - 1):\n",
    "            r = min(r,rampart[i][0] - rampart[i - 1][1] + rampart[i + 1][0] - rampart[i][1])\n",
    "        \n",
    "        def check(x):\n",
    "            lst = rampart[0][1]\n",
    "            for i in range(1,n - 1):\n",
    "                left = rampart[i][0] - lst\n",
    "                if left >= x:\n",
    "                    lst = rampart[i][1]\n",
    "                    continue\n",
    "                cnt = x - left\n",
    "                right = rampart[i + 1][0] - rampart[i][1]\n",
    "                if right >= cnt:\n",
    "                    lst = rampart[i][1] + cnt\n",
    "                else:\n",
    "                    return False\n",
    "            return True\n",
    "        \n",
    "        while l <= r:\n",
    "            mid = l + (r - l) // 2\n",
    "            if check(mid):\n",
    "                l = mid + 1\n",
    "            else:\n",
    "                r = mid - 1\n",
    "        return l - 1\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rampartDefensiveLine(self, rampart: List[List[int]]) -> int:\n",
    "        def fail(l):\n",
    "            last = -inf\n",
    "            for a, b in rampart:\n",
    "                if last > a: return 1\n",
    "                last = b + max(l - a + last, 0)\n",
    "            return 0\n",
    "\n",
    "        return bisect_left(range(rampart[-1][0] + 1), 1, key=fail) - 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import math\n",
    "class Solution:\n",
    "    def rampartDefensiveLine(self, rampart: List[List[int]]) -> int:\n",
    "        n = len(rampart)\n",
    "        min_gap = rampart[2][0] - rampart[0][1] - (rampart[1][1] - rampart[1][0])\n",
    "        all_gap = 0\n",
    "        l = r = 0\n",
    "        for i in range(1, n):\n",
    "            all_gap += rampart[i][0] - rampart[i-1][1]\n",
    "            if i < n-1:\n",
    "                min_gap = min(min_gap, rampart[i+1][0] - rampart[i-1][1] - (rampart[i][1] - rampart[i][0]))\n",
    "        r = min(min_gap,all_gap//(n-2))\n",
    "        def check(x):\n",
    "            lst = rampart[0][1]\n",
    "            for i in range(1, n-1):\n",
    "                left = rampart[i][0] - lst\n",
    "                if left >= x:\n",
    "                    lst = rampart[i][1]\n",
    "                    continue\n",
    "                cnt = x - left\n",
    "                right = rampart[i+1][0] - rampart[i][1]\n",
    "                if right >= cnt:\n",
    "                    lst = rampart[i][1] + cnt\n",
    "                else:\n",
    "                    return False\n",
    "            return True\n",
    "        while l <= r:\n",
    "            mid = l + (r-l) // 2\n",
    "            if check(mid):\n",
    "                l = mid + 1\n",
    "            else:\n",
    "                r = mid -1\n",
    "        return l-1\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rampartDefensiveLine(self, rampart: List[List[int]]) -> int:\n",
    "        def fail(l):\n",
    "            last = -inf\n",
    "            for a, b in rampart:\n",
    "                if last > a:\n",
    "                    return 1\n",
    "                left = max(l - a + last, 0)\n",
    "                last = b + left\n",
    "            return 0\n",
    "\n",
    "        return bisect_left(range(rampart[-1][-1] + 1), 1, key=fail) - 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rampartDefensiveLine(self, rampart: List[List[int]]) -> int:\n",
    "        n = len(rampart)\n",
    "        left = [0]*n \n",
    "        right = [0]*n\n",
    "        left[0] = float('inf')\n",
    "        right[n-1] = float('inf')\n",
    "        for i in range(1,n):\n",
    "            left[i] =  rampart[i][0] - rampart[i-1][1]\n",
    "            right[i-1] = rampart[i][0] - rampart[i-1][1]\n",
    "        def check(x):\n",
    "            rem = 0\n",
    "            for i in range(n):\n",
    "                rem = max(x + rem - left[i],0)\n",
    "                if(rem > right[i]):\n",
    "                    return False \n",
    "            return True\n",
    "        l, r = 0, 10**8\n",
    "        while(l <= r):\n",
    "            m = (l+r)>>1\n",
    "            if(check(m)):\n",
    "                l = m + 1\n",
    "            else:\n",
    "                r = m - 1\n",
    "        return r\n",
    "        "
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
